A simple scheme for the parallelization of particle filters and its application to the tracking of complex stochastic systems

摘要

We investigate the use of possibly the simplest scheme for theparallelisation of the standard particle filter, that consists in splitting thecomputational budget into $M$ fully independent particle filters with $N$particles each, and then obtaining the desired estimators by averaging over the$M$ independent outcomes of the filters. This approach minimises theparallelisation overhead yet displays highly desirable theoretical properties.Under very mild assumptions, we analyse the mean square error (MSE) of theestimators of 1-dimensional statistics of the optimal filtering distributionand show explicitly the effect of parallelisation scheme on the convergencerate. Specifically, we study the decomposition of the MSE into variance andbias components, to show that the former decays as $\frac{1}{MN}$, i.e.,linearly with the total number of particles, while the latter converges towards$0$ as $\frac{1}{N^2}$. Parallelisation, therefore, has the obvious advantageof dividing the running times while preserving the (asymptotic) performance ofthe particle filter. Following this lead, we propose a time-error index tocompare schemes with different degrees of parallelisation. Finally, we providetwo numerical examples. The first one deals with the tracking of a Lorenz 63chaotic system with dynamical noise and partial (noisy) observations, while thesecond example involves a dynamical network of modified FitzHugh-Nagumo (FH-N)stochastic nodes. The latter is a large dimensional system ($\approx3,000$state variables in our computer experiments) designed to numerically reproducetypical electrical phenomena observed in the atria of the human heart. In bothexamples, we show how the proposed parallelisation scheme attains the sameapproximation accuracy as a centralised particle filter with only a smallfraction of the running time, using a standard multicore computer.